//给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。 
//
// 
//
// 示例 1： 
// 
// 
//输入：head = [1,2,3,3,4,4,5]
//输出：[1,2,5]
// 
//
// 示例 2： 
// 
// 
//输入：head = [1,1,1,2,3]
//输出：[2,3]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点数目在范围 [0, 300] 内 
// -100 <= Node.val <= 100 
// 题目数据保证链表已经按升序 排列 
// 
//
// Related Topics 链表 双指针 👍 1280 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2024-03-25 21:58:37
 * @description 82.删除排序链表中的重复元素 II
 */
public class RemoveDuplicatesFromSortedListIi{
	 public static void main(String[] args) {
	 	 //测试代码
		 RemoveDuplicatesFromSortedListIi func = new RemoveDuplicatesFromSortedListIi();
		 Solution solution = func.new Solution();
		 ListNode head = func.new ListNode(1);
		 head.next = func.new ListNode(2);
		 head.next.next = func.new ListNode(3);
		 head.next.next.next = func.new ListNode(3);
		 head.next.next.next.next = func.new ListNode(4);
		 head.next.next.next.next.next = func.new ListNode(4);
		 head.next.next.next.next.next.next = func.new ListNode(5);
		 solution.deleteDuplicates(head);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for singly-linked list.
  public  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
		ListNode res=new ListNode(-101,head);
		ListNode p=res;
		ListNode pre=res;
		while (p != null && p.next != null) {
			if (p.next.val == p.val) {
				while (p.next != null && p.next.val == p.val) {
					p = p.next;
				}
				pre.next = p.next; // 直接跳过重复节点
				p = p.next;
			} else {
				pre = p;
				p = p.next;
			}
		}
		return res.next;
    }
	//官方寫法
	public ListNode deleteDuplicates1(ListNode head) {
		if (head == null) {
			return head;
		}

		ListNode dummy = new ListNode(0, head);

		ListNode cur = dummy;
		while (cur.next != null && cur.next.next != null) {
			if (cur.next.val == cur.next.next.val) {
				int x = cur.next.val;
				while (cur.next != null && cur.next.val == x) {
					cur.next = cur.next.next;
				}
			} else {
				cur = cur.next;
			}
		}

		return dummy.next;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
